置換群の部分群のk重推移性

証明:
$k$ に関する数学的帰納法を用いて、$1 \le m \le k$ を満たす任意の整数 $m$ に対して $G$ が $m$ 重推移的であることを示す。全域集合を $\Omega = \{1, 2, \dots, n\}$ とする。

【第1段： $m=1$ の場合】
仮定より、$G$ は長さ $n$ の巡回置換 $c_n$ を含む。$c_n$ は $\Omega$ のすべての要素を1つの巡回軌道としてつなぐため、$\Omega$ の任意の2要素 $x, y$ に対して、ある整数 $r \ge 0$ が存在して $(c_n)^r(x) = y$ となる。 $(c_n)^r \in G$ であるため、$G$ は $\Omega$ 上で推移的（ $1$ 重推移的）である。したがって $m=1$ のとき主張は成り立つ。

【第2段： $m-1$ から $m$ への帰納ステップ】
ある整数 $m$ （ $2 \le m \le k$ ）について、$G$ が $m-1$ 重推移的であると仮定する。このとき $G$ が $m$ 重推移的であることを示す。

仮定より、$G$ は長さ $n-m+1$ の巡回置換 $c_{n-m+1}$ を含む。 この巡回置換 $c_{n-m+1}$ は $\Omega$ のうちちょうど $n-m+1$ 個の要素を非自明に巡回させ、残りの $n - (n-m+1) = m-1$ 個の要素を固定する。 この固定される $m-1$ 個の要素からなる集合を $X = \{x_1, x_2, \dots, x_{m-1}\} \subset \Omega$ とする。

$X$ の点固定部分群を $G_X = \{g \in G \mid \text{任意の } 1 \le i \le m-1 \text{ について } g(x_i) = x_i\}$ とおく。 巡回置換の定義から明らかに $c_{n-m+1} \in G_X$ である。 $c_{n-m+1}$ は差集合 $\Omega \smallsetminus X$ のすべての元（計 $n-m+1$ 個）を単一のサイクルで巡回させるため、$G_X$ は集合 $\Omega \smallsetminus X$ 上で推移的に作用する。

ここで、$\Omega$ から互いに異なる $m$ 個の要素を選んだ任意の組を $(y_1, \dots, y_m)$ および $(z_1, \dots, z_m)$ とする。
帰納法の仮定より $G$ は $m-1$ 重推移的であるため、組 $(y_1, \dots, y_{m-1})$ を組 $(x_1, \dots, x_{m-1})$ に移す要素 $g \in G$ と、組 $(x_1, \dots, x_{m-1})$ を組 $(z_1, \dots, z_{m-1})$ に移す要素 $h \in G$ が存在する。すなわち、すべての $1 \le i \le m-1$ について以下が成り立つ。 $$\begin{aligned} g(y_i) &= x_i \\ h(x_i) &= z_i \end{aligned}$$ ここで、$y'_m = g(y_m)$ および $z'_m = h^{-1}(z_m)$ と定義する。 $g$ と $h$ は全単射であり、元の組の要素は互いに異なるため、$y'_m \notin \{x_1, \dots, x_{m-1}\} = X$ であり、同様に $z'_m \notin X$ である。 すなわち、$y'_m, z'_m \in \Omega \smallsetminus X$ である。

先述の通り $G_X$ は $\Omega \smallsetminus X$ 上で推移的であるため、$y'_m$ を $z'_m$ に移す要素 $f \in G_X$ が存在する。すなわち $f(y'_m) = z'_m$ であり、かつすべての $1 \le i \le m-1$ について $f(x_i) = x_i$ である。

以上の $g, f, h \in G$ を用いて、新たな置換 $w = h \circ f \circ g \in G$ を構成する。 この $w$ の作用を各 $i$ （ $1 \le i \le m$ ）について確認する。
$1 \le i \le m-1$ のとき： $$w(y_i) = h(f(g(y_i))) = h(f(x_i)) = h(x_i) = z_i$$ $i = m$ のとき： $$w(y_m) = h(f(g(y_m))) = h(f(y'_m)) = h(z'_m) = z_m$$ したがって、すべての $1 \le i \le m$ について $w(y_i) = z_i$ が成り立つ。 $(y_1, \dots, y_m)$ と $(z_1, \dots, z_m)$ は任意であったため、$G$ は $m$ 重推移的である。

【結論】
数学的帰納法により、$G$ は $k$ 重推移的であることが証明された。$\blacksquare$

証明:
全域集合を $\Omega = \{1, 2, \dots, n\}$ とし、仮定 2 に存在する $k-1$ 個の要素からなる部分集合を $A = \{a_1, a_2, \dots, a_{k-1}\}$ とする。
$H$ が $k$ 重推移的であることを示すためには、$\Omega$ の互いに異なる $k$ 個の要素からなる任意の2つの組 $(x_1, x_2, \dots, x_k)$ と $(y_1, y_2, \dots, y_k)$ に対して、ある $h \in H$ が存在して、すべての $1 \le i \le k$ について $h(x_i) = y_i$ を満たすことを示せばよい。

まず、組 $(x_1, \dots, x_k)$ に着目する。仮定 1 より $H$ は $(k-1)$ 重推移的であるため、組 $(x_1, \dots, x_{k-1})$ を組 $(a_1, \dots, a_{k-1})$ に移すような要素 $f \in H$ が存在する。すなわち、すべての $1 \le i \le k-1$ について $f(x_i) = a_i$ が成り立つ。
この $f$ によって $x_k$ が移る先を $x'_k = f(x_k)$ とおく。$f$ は全単射であり、元の組の要素は互いに異なるため、$x'_k$ は $a_1, \dots, a_{k-1}$ のいずれとも異なる。したがって $x'_k \notin A$ であり、$x'_k \in \Omega \smallsetminus A$ である。

同様に、組 $(y_1, \dots, y_k)$ についても、$H$ の $(k-1)$ 重推移性を用いる。組 $(y_1, \dots, y_{k-1})$ を組 $(a_1, \dots, a_{k-1})$ に移すような要素 $g \in H$ が存在する。すなわち、すべての $1 \le i \le k-1$ について $g(y_i) = a_i$ が成り立つ。
この $g$ によって $y_k$ が移る先を $y'_k = g(y_k)$ とおく。先ほどと同様の理由により、$y'_k \in \Omega \smallsetminus A$ である。

次に、$x'_k$ と $y'_k$ の関係について考える。仮定 2 より、$A$ を点ごとに固定する部分群 $H_A$ は補集合 $\Omega \smallsetminus A$ 上で推移的に作用する。$x'_k$ と $y'_k$ はともに $\Omega \smallsetminus A$ の要素であるため、$x'_k$ を $y'_k$ に移すような要素 $s \in H_A$ が存在する。すなわち、$s(x'_k) = y'_k$ を満たし、かつすべての $1 \le i \le k-1$ について $s(a_i) = a_i$ を満たす。

以上の $f, g, s \in H$ を組み合わせて、目的の置換 $h \in H$ を次のように構成する。 $$h = g^{-1} \circ s \circ f$$ この $h$ が、すべての $1 \le i \le k$ について $h(x_i) = y_i$ を満たすことを確認する。

$1 \le i \le k-1$ の場合： $$h(x_i) = g^{-1}(s(f(x_i))) = g^{-1}(s(a_i)) = g^{-1}(a_i) = y_i$$ $i = k$ の場合： $$h(x_k) = g^{-1}(s(f(x_k))) = g^{-1}(s(x'_k)) = g^{-1}(y'_k) = y_k$$ 以上により、任意の組 $(x_1, \dots, x_k)$ を $(y_1, \dots, y_k)$ に移す $h \in H$ を見つけることができた。したがって、$H$ は $k$ 重推移的である。$\blacksquare$